package leetcode.递归回溯BFSDFS;

/**
 *单词搜索
 *
 * DFS
 */
public class Test79单词搜索 {

    public static boolean exist(char[][] board, String word) {
        if (board.length == 0)
            return false;
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                // 对每一个点：i, j 开始上下左右递归搜索
                boolean isExisted = search(board, i, j, word, 0);
                if (isExisted)
                    return true;
            }
        }
        return false;
    }

    // index 是用来提取 words 对应的字符的，然后与数组中的对应元素进行匹配检查
    private static boolean search(char[][] board, int i, int j, String word, int index) {
        // 最后 index 大于 words 长度就说明全程匹配顺利
        if (index >= word.length())
            return true;
        // 否则就会在这里返回一个 false
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index))
            return false;
        /*
        对于每一个单词寻找他的下一个匹配项，可以规定从以顺时针方向寻找
        但是，题目不允许重复使用同一个单元格里面的字符，
        所以需要把用过的单元格标记起来，
        【防止回溯后在某一次遍历时再一次进入】
        标记的方式有很多种：boolean 数组，以及下面的 ^ 方式
         */
        board[i][j] ^= 255;
        // 递归上下左右搜索匹配的字符
        boolean res = search(board, i - 1, j, word, index + 1) ||
                search(board, i + 1, j, word, index + 1) ||
                search(board, i, j - 1, word, index + 1) ||
                search(board, i, j + 1, word, index + 1);
        // 再次异或255就能恢复成原来的字母
        board[i][j] ^= 255;
        return res;
    }

    public static void main(String[] args) { // 一个元素只能用一次
        char[][] board = {{'A', 'B', 'C', 'E'}, // 只能单向行走：往右走就不能回头往左走，除非不在本行；往下走就不能往回头往上走，除非不在本列
                          {'S', 'F', 'C', 'S'},
                          {'A', 'D', 'E', 'E'}
                         };
        String word = "ABCCED";
        System.out.println(exist(board, word));
    }
}
